Solution: Reverse Words in a String

Let's solve the Reverse Words in a String problem using the Two Pointers pattern.

Statement#

Given a sentence, reverse the order of its words without affecting the order of letters within a given word.

Constraints:

  • Sentence contains English uppercase and lowercase letters, digits, and spaces.
  • 11 ≤\leq sentence.length ≤\leq 10410^4
  • The order of the letters within a word is not to be reversed.

Note: The input string may contain leading or trailing spaces or multiple spaces between words. The returned string, however, should only have a single space separating each word. Do not include any extra spaces.

Solution#

In this problem, we first reverse the complete string. Now take two pointers, start and end, initialized with the start of the list, which is index 0.

Now, iterate a loop until start is less than the length of the list, and in each iteration, move the end pointer forward until it hits a space. At this point, we have a complete word starting from the start index to the end-1 index, but with the characters in reverse order.

To change the order of characters, we call the str_rev function with the starting and ending positions of the word. This will reverse the characters in the word.

Now, we update the start and end pointers to the next of end pointer, which is basically the first character of the next word. Now, repeat this process for the next word. At the end of all iterations, we get the reversed words in the string.

The following illustration shows these steps in detail:

Created with Fabric.js 3.6.6 Here's the sentence that we want to reverse. 0 1 2 3 4 5 6 7 8 9 10 11 H e l l o F r i e n d

1 of 20

Created with Fabric.js 3.6.6 As the first step, reverse the whole string. 0 1 2 3 4 5 6 7 8 9 10 11 d n e i r F o l l e H

2 of 20

Created with Fabric.js 3.6.6 start and end are initialized with 0. start: 0 0 1 2 3 4 5 6 7 8 9 10 11 d n e i r F o l l e H end: 0

3 of 20

Created with Fabric.js 3.6.6 start: 0 0 1 2 3 4 5 6 7 8 9 10 11 d n e i r F o l l e H end: 1 We keep incrementing end until a space or end of list is encountered.

4 of 20

Created with Fabric.js 3.6.6 Stop when we hit the space or end of text. start: 0 0 1 2 3 4 5 6 7 8 9 10 11 d n e i r F o l l e H end: 6

5 of 20

Created with Fabric.js 3.6.6 start_rev: 0 0 1 2 3 4 5 6 7 8 9 10 11 d n e i r F o l l e H end_rev: 5 Now, call the str_rev function by giving it the char array, start_rev, and end_rev-1as input arguments. Let's go through the in-place reverse of "dneirF".

6 of 20

Created with Fabric.js 3.6.6 start_rev: 0 0 1 2 3 4 5 6 7 8 9 10 11 F n e i r d o l l e H end_rev: 5 Swap the chars at the start_rev and end_rev indexes.

7 of 20

Created with Fabric.js 3.6.6 Increment start_rev, and decrement end_rev. start_rev: 1 0 1 2 3 4 5 6 7 8 9 10 11 F n e i r d o l l e H end_rev: 4

8 of 20

Created with Fabric.js 3.6.6 start_rev: 1 0 1 2 3 4 5 6 7 8 9 10 11 F r e i n d o l l e H end_rev: 4 Swap the chars at the start_rev and end_rev indexes.

9 of 20

Created with Fabric.js 3.6.6 Increment start_rev, and decrement end_rev. start_rev: 2 0 1 2 3 4 5 6 7 8 9 10 11 F r e i n d o l l e H end_rev: 3

10 of 20

Created with Fabric.js 3.6.6 start_rev: 2 0 1 2 3 4 5 6 7 8 9 10 11 F r i e n d o l l e H end_rev: 3 Swap the chars at the start_rev and end_rev indexes.

11 of 20

Created with Fabric.js 3.6.6 Increment start_rev, and decrement end_rev.Since start_rev > end_rev, the function returns. start_rev: 3 0 1 2 3 4 5 6 7 8 9 10 11 F r i e n d o l l e H end_rev: 2

12 of 20

Created with Fabric.js 3.6.6 start: 7 0 1 2 3 4 5 6 7 8 9 10 11 F r i e n d o l l e H end: 7 In the reverse_words function, startand end are both set to end+1.

13 of 20

Created with Fabric.js 3.6.6 start: 7 0 1 2 3 4 5 6 7 8 9 10 11 F r i e n d o l l e H end: 8 We keep incrementing end until we hit end of the list.

14 of 20

Created with Fabric.js 3.6.6 Stop when we hit the space or end of text. start: 7 0 1 2 3 4 5 6 7 8 9 10 11 F r i e n d o l l e H end: 12

15 of 20

Created with Fabric.js 3.6.6 start_rev: 7 0 1 2 3 4 5 6 7 8 9 10 11 F r i e n d o l l e H end_rev: 11 Now, call the str_rev function by giving it the char array, start_rev, and end_rev-1 as input arguments.

16 of 20

Created with Fabric.js 3.6.6 Reverse the substring. start_rev: 9 0 1 2 3 4 5 6 7 8 9 10 11 F r i e n d H e l l o end_rev: 9

17 of 20

Created with Fabric.js 3.6.6 start: 7 0 1 2 3 4 5 6 7 8 9 10 11 F r i e n d H e l l o end: 12 In the reverse_words function:

18 of 20

Created with Fabric.js 3.6.6 start: 12 0 1 2 3 4 5 6 7 8 9 10 11 F r i e n d H e l l o end: 12 start and end are both set to end+1.Since start is greater than the length of the list, we stop here.

19 of 20

Created with Fabric.js 3.6.6 0 1 2 3 4 5 6 7 8 9 10 11 F r i e n d H e l l o The final sentence with the placement of words reversed:

20 of 20

We can see the code of this solution below.

Reverse Words in a String

Time complexity#

Since the array is traversed twice, the time complexity of this solution is O(n+n)=O(n)O(n + n) = O(n), where nn is the length of the string.

Space complexity#

The space complexity of this solution is O(n)O(n), since, at the start of the algorithm we copy it into a list of characters to overcome the issue of strings being immutable in Python.

Reverse Words in a String

Valid Palindrome II